package algotithm.jianzhioffer.test33;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author zhouyanxiang
 * @Date 2020-12-2020/12/22-9:50
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {1, 3, 2, 6, 5};
        boolean flag = solution.verifyPostorder(arr);
        System.out.println(flag);
    }

    public boolean verifyPostorder(int[] postorder) {
        Deque<Integer> deque = new ArrayDeque<>();
        int root = Integer.MAX_VALUE;
        for (int i = postorder.length - 1; i > 0; i--) {
            if (postorder[i] > root) {
                return false;
            }
            while (!deque.isEmpty() && postorder[i] < deque.peek()) {
                root = deque.pop();
            }
            deque.push(postorder[i]);
        }
        return true;
    }


}
